package codingforgreat.class43;


import com.sun.deploy.util.SystemUtils;
import sun.nio.cs.ext.EUC_JP_LINUX;
import sun.plugin2.util.SystemUtil;

import java.util.Arrays;

// 来自360笔试
// 给定一个正数数组arr，长度为n，下标0~n-1
// arr中的0、n-1位置不需要达标，它们分别是最左、最右的位置
// 中间位置i需要达标，达标的条件是 : arr[i-1] > arr[i] 或者 arr[i+1] > arr[i]哪个都可以
// 你每一步可以进行如下操作：对任何位置的数让其-1
// 你的目的是让arr[1~n-2]都达标，这时arr称之为yeah！数组
// 返回至少要多少步可以让arr变成yeah！数组
// 数据规模 : 数组长度 <= 10000，数组中的值<=500
public class Class02_MinCostToYeah {
    public static final int INVALID = Integer.MAX_VALUE;

    // 纯暴力方法，只是为了结果对
    // 时间复杂度极差
    public static int minCost0(int[] arr) {
     if(arr == null || arr.length == 0){
         return 0;
     }
     int n = arr.length;
     int min = arr[0];
        for (int i = 0; i < n; i++) {
            if(arr[i] < min){
                min = arr[i];
            }
        }
     int base = min - n;
     return process0(arr,base,0);
    }

    public static int process0(int[] arr, int base, int index) {
        if (index == arr.length) {
            for (int i = 1; i < arr.length - 1; i++) {
                if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1]) {
                    return INVALID;
                }
            }
            return 0;
        }

            int ans = INVALID;
            int tmp = arr[index];
            for (int cost = 0; arr[index] >= base; cost++ ,arr[index]--) {
                int next = process0(arr,base,index + 1);
                if(next != INVALID){
                    ans = Math.min(ans,cost + next);
                }
            }
            arr[index] = tmp;
            return ans;
    }

    // 递归方法，已经把尝试写出
    public static int minCost1(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int min = INVALID;
        for (int num : arr) {
            min = Math.min(min, num);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] += arr.length - min;
        }
        return process1(arr, 1, arr[0], true);
    }

    // 当前来到index位置，值arr[index]
    // pre : 前一个位置的值，可能减掉了一些，所以不能用arr[index-1]
    // preOk : 前一个位置的值，是否被它左边的数变有效了
    // 返回 : 让arr都变有效，最小代价是什么？
    public static int process1(int[] arr, int index, int pre, boolean preOk) {
        if (index == arr.length - 1) { // 已经来到最后一个数了
            return preOk || pre < arr[index] ? 0 : INVALID;
        }
        // 当前index，不是最后一个数！
        int ans = INVALID;
        if (preOk) {
            for (int cur = arr[index]; cur >= 0; cur--) {
                int next = process1(arr, index + 1, cur, cur < pre);
                if (next != INVALID) {
                    ans = Math.min(ans, arr[index] - cur + next);
                }
            }
        } else {
            for (int cur = arr[index]; cur > pre; cur--) {
                int next = process1(arr, index + 1, cur, false);
                if (next != INVALID) {
                    ans = Math.min(ans, arr[index] - cur + next);
                }
            }
        }
        return ans;
    }

    // 初改动态规划方法，就是参考minCost1，改出来的版本
    public static int minCost2(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int min = INVALID;
        for (int num : arr) {
            min = Math.min(min, num);
        }
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            arr[i] += n - min;
        }
        int[][][] dp = new int[n][2][];
        for (int i = 1; i < n; i++) {
            dp[i][0] = new int[arr[i - 1] + 1];
            dp[i][1] = new int[arr[i - 1] + 1];
            Arrays.fill(dp[i][0], INVALID);
            Arrays.fill(dp[i][1], INVALID);
        }
        for (int pre = 0; pre <= arr[n - 2]; pre++) {
            dp[n - 1][0][pre] = pre < arr[n - 1] ? 0 : INVALID;
            dp[n - 1][1][pre] = 0;
        }
        for (int index = n - 2; index >= 1; index--) {
            for (int pre = 0; pre <= arr[index - 1]; pre++) {
                for (int cur = arr[index]; cur > pre; cur--) {
                    int next = dp[index + 1][0][cur];
                    if (next != INVALID) {
                        dp[index][0][pre] = Math.min(dp[index][0][pre], arr[index] - cur + next);
                    }
                }
                for (int cur = arr[index]; cur >= 0; cur--) {
                    int next = dp[index + 1][cur < pre ? 1 : 0][cur];
                    if (next != INVALID) {
                        dp[index][1][pre] = Math.min(dp[index][1][pre], arr[index] - cur + next);
                    }
                }
            }
        }
        return dp[1][1][arr[0]];
    }

    // minCost2动态规划 + 枚举优化
    // 改出的这个版本，需要一些技巧，但很可惜不是最优解
    // 虽然不是最优解，也足以通过100%的case了，
    // 这种技法的练习，非常有意义
    public static int minCost3(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int min = INVALID;
        for (int num : arr) {
            min = Math.min(min, num);
        }
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            arr[i] += n - min;
        }
        int[][][] dp = new int[n][2][];
        for (int i = 1; i < n; i++) {
            dp[i][0] = new int[arr[i - 1] + 1];
            dp[i][1] = new int[arr[i - 1] + 1];
        }
        for (int p = 0; p <= arr[n - 2]; p++) {
            dp[n - 1][0][p] = p < arr[n - 1] ? 0 : INVALID;
        }
        int[][] best = best(dp, n - 1, arr[n - 2]);
        for (int i = n - 2; i >= 1; i--) {
            for (int p = 0; p <= arr[i - 1]; p++) {
                if (arr[i] < p) {
                    dp[i][1][p] = best[1][arr[i]];
                } else {
                    dp[i][1][p] = Math.min(best[0][p], p > 0 ? best[1][p - 1] : INVALID);
                }
                dp[i][0][p] = arr[i] <= p ? INVALID : best[0][p + 1];
            }
            best = best(dp, i, arr[i - 1]);
        }
        return dp[1][1][arr[0]];
    }

    public static int[][] best(int[][][] dp, int i, int v) {
        int[][] best = new int[2][v + 1];
        best[0][v] = dp[i][0][v];
        for (int p = v - 1; p >= 0; p--) {
            best[0][p] = dp[i][0][p] == INVALID ? INVALID : v - p + dp[i][0][p];
            best[0][p] = Math.min(best[0][p], best[0][p + 1]);
        }
        best[1][0] = dp[i][1][0] == INVALID ? INVALID : v + dp[i][1][0];
        for (int p = 1; p <= v; p++) {
            best[1][p] = dp[i][1][p] == INVALID ? INVALID : v - p + dp[i][1][p];
            best[1][p] = Math.min(best[1][p], best[1][p - 1]);
        }
        return best;
    }

    // 最终的最优解，贪心
    // 时间复杂度O(N)
    // 请注意，重点看上面的方法
    // 这个最优解容易理解，但让你学到的东西不是很多
    public static int yeah(int[] arr) {
        if (arr == null || arr.length < 3) {
            return 0;
        }
        int n = arr.length;
        int[] nums = new int[n + 2];
        nums[0] = Integer.MAX_VALUE;
        nums[n + 1] = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            nums[i + 1] = arr[i];
        }
        int[] leftCost = new int[n + 2];
        int pre = nums[0];
        int change = 0;
        for (int i = 1; i <= n; i++) {
            change = Math.min(pre - 1, nums[i]);
            leftCost[i] = nums[i] - change + leftCost[i - 1];
            pre = change;
        }
        int[] rightCost = new int[n + 2];
        pre = nums[n + 1];
        for (int i = n; i >= 1; i--) {
            change = Math.min(pre - 1, nums[i]);
            rightCost[i] = nums[i] - change + rightCost[i + 1];
            pre = change;
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= n; i++) {
            ans = Math.min(ans, leftCost[i] + rightCost[i + 1]);
        }
        return ans;
    }

    // 为了测试
    public static int[] randomArray(int len, int v) {
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * v) + 1;
        }
        return arr;
    }

    // 为了测试
    public static int[] copyArray(int[] arr) {
        int[] ans = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ans[i] = arr[i];
        }
        return ans;
    }

    // 为了测试
    public static void main(String[] args) {
        int len = 7;
        int v = 10;
        int testTime = 100;
        System.out.println("==========");
        System.out.println("功能测试开始");
        for (int i = 0; i < testTime; i++) {
            int n = (int) (Math.random() * len) + 1;
            int[] arr = randomArray(n, v);
            int[] arr0 = copyArray(arr);
            int[] arr1 = copyArray(arr);
            int[] arr2 = copyArray(arr);
            int[] arr3 = copyArray(arr);
            int[] arr4 = copyArray(arr);
            int ans0 = minCost0(arr0);
            int ans1 = minCost1(arr1);
            int ans2 = minCost2(arr2);
            int ans3 = minCost3(arr3);
            int ans4 = yeah(arr4);
            if (ans0 != ans1 || ans0 != ans2 || ans0 != ans3 || ans0 != ans4) {
                System.out.println("出错了！");
            }
        }
        System.out.println("功能测试结束");
        System.out.println("==========");

        System.out.println("性能测试开始");

        len = 10000;
        v = 500;
        System.out.println("生成随机数组长度：" + len);
        System.out.println("生成随机数组值的范围：[1, " + v + "]");
        int[] arr = randomArray(len, v);
        int[] arr3 = copyArray(arr);
        int[] arrYeah = copyArray(arr);
        long start;
        long end;
        start = System.currentTimeMillis();
        int ans3 = minCost3(arr3);
        end = System.currentTimeMillis();
        System.out.println("minCost3方法:");
        System.out.println("运行结果: " + ans3 + ", 时间(毫秒) : " + (end - start));

        start = System.currentTimeMillis();
        int ansYeah = yeah(arrYeah);
        end = System.currentTimeMillis();
        System.out.println("yeah方法:");
        System.out.println("运行结果: " + ansYeah + ", 时间(毫秒) : " + (end - start));
        System.out.println("性能测试结束");
        System.out.println("==========");

    }

}
